The puzzle:
You place 100 coins heads up in a row and number them by position, with the coin all the way on the left No. 1 and the one on the rightmost edge No. 100. Next, for every number N, from 1 to 100, you flip over every coin whose position is a multiple of N. For example, first you'll flip over all the coins, because every number is a multiple of 1. Then you'll flip over all the even-numbered coins, because they're multiples of 2. Then you'll flip coins No. 3, 6, 9, 12, and so on.
What do the coins look like when you're done? Specifically, which coins are heads down?
Answer:
-++-++++-++++++-++++++++-++++++++++-++++++++++++-++++++++++++++-++++++++++++++++-++++++++++++++++++-
Discussion:
I chose this puzzle out of 7 because it looked interesting from both a mathematical and programming angle and also easily implementable. If I had not solved this puzzle using an algorithm I would have spent most of my time tediously flipping coins and hopefully keeping track accurately instead I spent most of my time tediously working out bugs with my algorithm. That's not to say that the irony made the puzzle any less enjoyable.
Not only did this puzzle have an interesting programming angle, while solving the problem which took three attempts on my part I found myself wondering what the mathematical basis for this problem is. My algorithm asks for each coin and step (the step we can let be N), "Is the coin's number divisible by N such that it becomes equal to 0?" If yes, we flip the coin. This is a different question than "Is the coin's number a multiple of N?", which implicates a couple of things. One, my algorithm wouldn't be able to work with negative numbers, more on that in a second. Two, also that it wouldn't be able to work with decimals or non-whole numbers, because it counts each step using whole numbers. Not a huge problem for the purpose of this puzzle because non-whole coins aren't a part of this puzzle and would be unusual. Finally and most fascinating, this puzzle seems to have a basic formula that if used, much larger amounts of coins would be solvable with the same flip puzzle.
The Algorithm:
In [24]:
import sys
sys.path.append('../')
from coins import *
In [25]:
coins = flip_coins(100)
print(coins)
In [26]:
coins = flip_coins(100, all_flips=True)
Some math:
As N becomes greater so does the frequency between coin flips. Interestingly, the amount of coins flipped decreases by 1/3 with each flip. So we get the exponential nature of the puzzle seen above.
In [27]:
sqaured = (lambda n: n ** 2)
sqaured(20)
Out[27]:
In [28]:
print([(sqaured(i) // 2) for i in range(1, 100)])
Source code:
""" coins.py | Tue, Feb 07, 2017 | Roman S. Collins The problem: You place 100 coins heads up in a row and number them by position, with the coin all the way on the left No. 1 and the one on the rightmost edge No. 100. Next, for every number N, from 1 to 100, you flip over every coin whose position is a multiple of N. For example, first you'll flip over every coin whose position is a multiple of N. For example. First you'll flip over all the coins, because every number is a multiple of 1. Then you'll flip over all the even-numbered coins, because theyre multiples of 2. Then you'll flip coins No. 3, 6, 9, 12 and so on. """ def flip_coins(n, all_flips=False): coins = [x for x in range(n + 1)] coins[0] = None coins.append(None) flip_coins = ['+' for i in range(n + 1)] flip_coins[0] = '' for n in range(1, len(coins) - 1): for z in range(1, n + 1): if (coins[n] % z == 0): flip_coins[n] = flip(flip_coins[n]) if all_flips == True: print(''.join(flip_coins)) if all_flips == False: print(''.join(flip_coins)) def flip(coin): if coin == '+': coin = '-' elif coin == '-': coin = '+' return coin def also_interesting(): # Mostly just saving for later # to test and see if solving the problem # may be faster with something kinda # like this for y in range(1, 101): #print(termcolor.colored('.', 'red')) print('Flip#{}: '.format(y), end='') #if (y != 1) or (y != 0): flip = [x for x in range(0, 101, y)] print(len(flip)) print(flip) def main(): coins = flip_coins(100) if __name__ == '__main__': main()
In [ ]: